package com.suanfa.sort;

/**
 * Created by buguniao on 16/2/21.
 */
public class QuickSort extends SuanFaTemplate {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        double[] arr = quickSort.getRandomArray(100000);
        long time = quickSort.run(arr);
        System.out.println("time cost : " + time);
//        System.out.println(Arrays.toString(arr));
    }

    @Override
    public long run(double[] arr) {
        long t1= System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long t2=System.currentTimeMillis();
        return t2-t1;
    }

    public void sort(double[] arr,int lo,int hi){
        if(lo>hi){
            return;
        }
        double v= arr[lo];
        int i=lo;
        int j=hi;

        while(i!=j){
            while(i<j && arr[j]>=v){
                j--;
            }
            while(i<j && arr[i]<=v){
                i++;
            }
            if(i<j){
                exchange(arr,i,j);
            }
        }
        double t = arr[i];
        arr[i]=v;
        arr[lo]=t;

        sort(arr,lo,i-1);
        sort(arr,i+1,hi);
    }
}
